import java.util.Map;
import java.util.Objects;
import java.util.TreeMap;

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        TreeMap<Long, Integer> treeMap = new TreeMap<>();
        treeMap.put(0L, 1);
        long sum = 0;
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            for (int value : treeMap.subMap(sum - upper, true, sum - lower, true).values()) {
                cnt += value;
            }
            treeMap.put(sum, treeMap.getOrDefault(sum, 0) + 1);
        }
        return cnt;
    }
}
